// @algorithm @lc id=100307 lang=cpp
// @title xu-lie-hua-er-cha-shu-lcof

#include "algm/algm.h"
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode *root) {
        string ans{};
        if (root == nullptr) {
            return ans;
        }
        queue<TreeNode *> q;
        q.push(root);
        bool validString = true;
        while (!q.empty() && validString) {
            int cnt = q.size();
            string s = {};
            validString = false;
            while (cnt--) {
                TreeNode *temp = q.front();
                q.pop();
                if (temp == nullptr) {
                    s += "null,";
                }
                else {
                    validString = true;
                    s += (to_string(temp->val) + ",");
                    q.push(temp->left);
                    q.push(temp->right);
                }
            }
            // 这一层有有用数据
            if (validString) {
                ans += s;
            }
        }
        ans.pop_back();
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data) {
        if (data.empty()) {
            return nullptr;
        }
        data += ",";
        int n = data.size();
        int commaPos = 0;
        while (data[commaPos] != ',') {
            ++commaPos;
        }
        TreeNode *root = new TreeNode(stoi(data.substr(0, commaPos)));
        int preCommaPos = commaPos;
        ++commaPos;
        queue<TreeNode *> q;
        q.push(root);
        bool isLeftSon = true;
        while (commaPos < n - 1) {
            int cnt = q.size();
            while (cnt--) {
                TreeNode *temp = q.front();
                q.pop();
                for (int i = 0; i < 2; ++i) {
                    while (data[commaPos] != ',') {
                        ++commaPos;
                    }
                    string s = data.substr(preCommaPos + 1, commaPos - preCommaPos - 1);
                    preCommaPos = commaPos;
                    ++commaPos;
                    if (s == "null") {
                        isLeftSon ? temp->left = nullptr : temp->right = nullptr;
                        isLeftSon = !isLeftSon;
                    }
                    else {
                        TreeNode *newNode = new TreeNode(stoi(s));
                        isLeftSon ? temp->left = newNode : temp->right = newNode;
                        isLeftSon = !isLeftSon;
                        q.push(newNode);
                    }
                }
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));